package gold.digger;

import java.util.*;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC433 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minMutation(String start, String end, String[] bank) {
            boolean[][] graph = new boolean[bank.length + 1][bank.length + 1];
            int targetIndex = -1;
            for (int i = 0; i < bank.length; i++) {
                if (bank[i].equals(end)) {
                    targetIndex = i + 1;
                }

                if (isLink(start, bank[i])) graph[0][i + 1] = true;

                for (int j = 0; j < bank.length; j++) {
                    if (isLink(bank[i], bank[j])) graph[i + 1][j + 1] = true;
                }
            }

            //BFS找最短路
            int step = 0;
            Queue<Integer> queue = new LinkedList<>();
            Set<Integer> visited = new HashSet<>();
            queue.offer(0);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int cur = queue.poll();
                    if (cur == targetIndex) return step;
                    visited.add(cur);

                    for (int j = 0; j <= bank.length; j++) {
                        if (j == cur || !graph[cur][j] || visited.contains(j)) continue;
                        queue.offer(j);
                    }
                }
                ++step;
            }

            return -1;
        }

        public boolean isLink(String from, String to) {
            if (from.length() != to.length()) return false;
            int diffCount = 0;
            for (int i = 0; i < from.length(); i++) {
                if (from.charAt(i) != to.charAt(i)) ++diffCount;
            }

            return diffCount == 1;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String[] arr = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        System.out.println(solution.minMutation("AACCGGTT", "AACCGGTA", new String[0]));
    }

    public static void main(String[] args) throws Exception {
        LC433 an = new LC433();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
